# https://leetcode.cn/problems/count-numbers-with-unique-digits/description/
# 357. 统计各位数字都不同的数字个数
# medium, 刘小康 2024.09.19
# 数位DP

class Solution:
    def countNumbersWithUniqueDigits(self, n: int) -> int:
        match n:
            case 0:
                return 1
            case 1:
                return 10
            case _:
                ans = 9
                flag = 9
                for i in range(1, n):
                    ans *= flag
                    flag -= 1
                return ans + self.countNumbersWithUniqueDigits(n - 1)
